package com.future;

import com.future.util.TreeNode;

import java.util.LinkedList;

/**
 * Description: 230. 二叉搜索树中第K小的元素
 *
 * @author weiruibai.vendor
 * Date: 2022/10/31 14:17
 */
public class Solution_230 {


    public static void main(String[] args) {
        Solution_230 solution_230 = new Solution_230();
        TreeNode head = new TreeNode(10);
        head.left = new TreeNode(5);
        head.right = new TreeNode(20);
        head.left.left = new TreeNode(2);
        head.left.right = new TreeNode(8);
        head.left.left.left = new TreeNode(1);
        head.left.left.right = new TreeNode(3);
        int k = 3;
        System.out.println(solution_230.kthSmallest(head, k));
        head = new TreeNode(5);
        head.left = new TreeNode(3);
        head.right = new TreeNode(6);
        head.left.left = new TreeNode(2);
        head.left.right = new TreeNode(4);
        head.left.left.left = new TreeNode(1);
        head.left.left.right = new TreeNode(3);
        k = 3;
        System.out.println(solution_230.kthSmallest(head, k));
    }

    public int kthSmallest(TreeNode root, int k) {
        LinkedList<Integer> lined = new LinkedList<>();
        process(root, lined, k);
        return lined.getLast();
    }


    private void process(TreeNode root, LinkedList<Integer> linkedList, int k) {
        if (linkedList.size() == k) {
            return;
        }
        if (root == null) {
            return;
        }
        process(root.left, linkedList, k);
        if (linkedList.size() == k) {
            return;
        }
        linkedList.add(root.val);
        process(root.right, linkedList, k);
    }
}
